Traffic engineering, in its simplest form, attempts to meet the quality of service (QOS) needs of multiple users by making the best use of limited network resources. Traffic engineering also can be used to ensure that a packet or data source adheres to a stipulated contract.
Two basic types of traffic engineering mechanisms include; traffic policing mechanisms (policers) and traffic shaping mechanisms (shapers). Policers and shapers both use a packet's traffic descriptor, indicated by the packet's classification, to ensure QOS and adherence to the stipulated contract by a given data source. Policers and shapers typically identify traffic descriptor violations in a similar manner. However, policers and shapers usually differ in the way they respond to violations; a policer will typically drop the excess traffic, whereas a shaper will typically delay excess traffic using a buffer, or queuing mechanism, to hold packets and shape the flow when the data rate of the source is higher than expected.
Credit buckets, also known as token buckets, are mechanisms that can be used to implement policers and/or shapers. A credit bucket has three components: a burst size, a mean rate, and a time interval (Tc). The three components are related to each other according to the following equation: mean rate=burst size/time interval. The mean rate specifies how much data can be sent or forwarded per unit time on average. The burst size specifies, usually in bits per burst, how much data can be sent per a given unit of time while avoiding scheduling concerns. The time interval is the measurement interval and specifies the time quantum, for example, in seconds per burst.
Utilizing a credit bucket algorithm, each credit provides permission to forward a certain number of bits within a network. A bucket holds credits for a particular class of network traffic and credits are added into the bucket at a specified rate. For example, a fixed number of credits is added to the credit bucket at fixed time intervals. To forward a packet, a number of credits equal in bit size to the packet must be removed from the bucket. For example, if each credit represents 1,000 bits then a packet of 100,000 bits will have an equivalent credit value of 100 credits. If the number of credits in the bucket is equal to or exceeds the credit requirement of the packet, then the packet is forwarded. If, however, the number of credits in the bucket is below the credit requirement of the packet, then the packet is either held until the bucket has enough credits to forward the packet or the packet is dropped.
Credit buckets continue to accumulate credits even when there is no traffic to forward. In order to limit the magnitude of the traffic bursts, the accumulation of credits in a bucket can be capped at a maximum value. When a credit bucket reaches its maximum value, additional credits are no longer accumulated.
In communications networks that classify traffic into multiple traffic classes, traffic engineering mechanisms, such as credit buckets, are typically implemented on a per-class basis. When using credit buckets as traffic engineering mechanism as described above, the credit buckets must all be periodically updated (i.e. refreshed with new credits). In typical credit bucket implementations, the credit buckets are updated during the same time interval. For example, every credit bucket is updated every one microsecond (μs). FIG. 1A depicts an embodiment of a prior art system comprising one-hundred (100) credit buckets that are each updated at every time interval. FIG. 1B depicts a graph of credits per bucket as a function of elapsed time for a specific one of the one-hundred buckets depicted in FIG. 1A, i.e., bucket zero (0). As the graph indicates, since the credit bucket is updated at every time interval, the number of credits in the bucket at a particular time is a function of the number of time intervals that have elapsed. For example, at any time X, the number of credits in bucket zero is equal to [(X)*(credit bucket refresh rate)], assuming no credits have been removed as a result of forwarding packets.
Although updating each credit bucket at every time interval works well to provide a constant refresh rate to the credit buckets, refreshing every credit bucket during every time interval becomes problematic as the number of credit buckets increases. Specifically, the amount of hardware resources that are required to update every credit bucket at every time interval are costly, both financially and also in terms of the real estate required on the integrated circuits used in such an implementation. Therefore, what is needed is a resource-efficient credit bucket mechanism that can scale to a large number of credit buckets.